/**
 * 折半查找：又称之为二分查找，它仅适用于有序的顺序表；
 * 折半查找不适用于链式查找。仅适用于有序的顺序查找；
 * 查找成功的平均查找长度为:ASL=log2(n+1)-1
 */
typedef int ElemType;
typedef struct{
	ElemType *data;	//元素存储空间基址
	int len;		//线性表表的长度
}SSTable;

int Binary_Search(SSTable* T, ElemType key)
{
	int low=0,high=T->len-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(T->data[mid]==key) return mid;
		else if(T->data[mid]>key) high=mid-1;	//从前半部分继续查找
		else low=mid+1;		//从后半部分继续查找
	}
	return -1;	//找不到就返回-1
}